//https://leetcode.cn/problems/count-special-integers/submissions/575168208/

class Solution {
public:
    // 预先计算阶乘的常量数组
    static constexpr int fac[] = {
        1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800
    };
    
    // 计算从 0 到 pos-1 位上可选择的数字个数
    static constexpr int cnt(int state, int pos) {
        return __builtin_popcount(((1 << pos) - 1) & ~state);
    }
    
    int countSpecialNumbers(int n) {
        const string num = to_string(n); // 将 n 转换为字符串，方便逐位处理
        const int m = num.size(); // n 的位数
        int ans = 0;
        int p = 0;
        int used = 0; // 用来记录已经使用过的数字
        
        // 从高位开始处理，计算符合条件的特殊整数
        for (; p < m; ++p) {
            // 计算当前位能填入的数字数量（从 0 到 num[p] - 1）
            ans += cnt(used, num[p] - '0') * fac[9 - p] / fac[10 - m];
            if (used >> (num[p] - '0') & 1) break; // 如果当前位的数字已被使用，结束循环
            used |= 1 << (num[p] - '0'); // 标记当前数字已被使用
        }
        ans += p == m; // 如果所有位都处理完成，说明 n 本身是一个特殊整数，结果加 1
        
        // 计算所有比 n 位数小的特殊整数数量
        for (int i = 1; i < m; ++i)
            ans += 9 * fac[9] / fac[10 - i];
        
        return ans - fac[9] / fac[10 - m]; // 去除掉位数为 m 且所有位数字不同的总数
    }
};